package com.example.summary.leetcode;

//合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
//
// 示例:
//
// 输入:
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//输出: 1->1->2->3->4->4->5->6
//

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

public class LeetCode23 {

    public static final ListNode NULL = null;

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode listNode1 = new ListNode(-495, new ListNode(-480, new ListNode(-474, null)));
    static ListNode listNode2 = new ListNode(-499, new ListNode(-497, new ListNode(-491, null)));
    static ListNode listNode3 = new ListNode(-500, new ListNode(-499, new ListNode(-498, null)));
    static ListNode listNode4 = new ListNode(-496, new ListNode(-490, new ListNode(-453, null)));
    static ListNode listNode5 = new ListNode(-473, new ListNode(-319, new ListNode(-313, null)));
    static ListNode listNode6 = new ListNode(-454, new ListNode(-443, new ListNode(-442, null)));
    static ListNode listNode7 = NULL;
    static ListNode listNode8 = new ListNode(-492, new ListNode(-476, new ListNode(-467, null)));
    static ListNode listNode9 = new ListNode(-500, new ListNode(-500, new ListNode(-497, null)));
    static ListNode listNode10 = new ListNode(-479, new ListNode(-471, new ListNode(-467, null)));
    static ListNode listNode11 = new ListNode(-498, new ListNode(-498, new ListNode(-496, null)));
    static ListNode listNode12 = new ListNode(-459, new ListNode(-432, new ListNode(-414, null)));
    static ListNode listNode13 = new ListNode(-459, new ListNode(-421, new ListNode(-413, null)));
    static ListNode listNode14 = new ListNode(-496, new ListNode(-489, new ListNode(-448, null)));
    static ListNode listNode15 = new ListNode(-497, new ListNode(-487, new ListNode(-484, null)));
    static ListNode listNode16 = new ListNode(-495, new ListNode(-490, new ListNode(-486, null)));
    static ListNode listNode17 = new ListNode(-498, new ListNode(-481, new ListNode(-478, null)));
    static ListNode listNode18 = new ListNode(-483, new ListNode(-464, new ListNode(-460, null)));
    static ListNode listNode19 = new ListNode(-498, new ListNode(-490, new ListNode(-488, null)));
    static ListNode listNode20 = new ListNode(-324, new ListNode(-11, null));
    static ListNode listNode21 = new ListNode(-499, new ListNode(-496, new ListNode(-493, null)));
    static ListNode listNode22 = new ListNode(-497, new ListNode(-496, new ListNode(-460, null)));
    static ListNode listNode23 = new ListNode(-489, new ListNode(-485, new ListNode(-483, null)));
    static ListNode listNode24 = new ListNode(-492, new ListNode(-488, new ListNode(-472, null)));
    static ListNode listNode25 = new ListNode(-487, new ListNode(-481, new ListNode(-474, null)));
    static ListNode listNode26 = new ListNode(-492, new ListNode(-480, new ListNode(-454, null)));
    static ListNode listNode27 = new ListNode(-496, new ListNode(-495, new ListNode(-493, null)));
    static ListNode listNode28 = new ListNode(-486, new ListNode(-476, new ListNode(-475, null)));
    static ListNode listNode29 = new ListNode(-487, new ListNode(-486, new ListNode(-484, null)));
    static ListNode listNode30 = new ListNode(-494, new ListNode(-494, new ListNode(-493, null)));
    static ListNode listNode31 = new ListNode(-405, null);
    static ListNode listNode32 = new ListNode(-493, new ListNode(-486, new ListNode(-482, null)));
    static ListNode listNode33 = new ListNode(-500, new ListNode(-498, new ListNode(-488, null)));
    static ListNode listNode34 = new ListNode(-499, new ListNode(-492, new ListNode(-479, null)));
    static ListNode listNode35 = new ListNode(-498, new ListNode(-497, new ListNode(-495, null)));
    static ListNode listNode36 = new ListNode(-492, new ListNode(-487, new ListNode(-486, null)));
    static ListNode listNode37 = new ListNode(-500, new ListNode(-492, new ListNode(-487, null)));
    static ListNode listNode38 = new ListNode(-493, new ListNode(-490, new ListNode(-476, null)));
    static ListNode listNode39 = new ListNode(-273, new ListNode(-227, null));
    static ListNode listNode40 = new ListNode(-498, new ListNode(-493, new ListNode(-488, null)));
    static ListNode listNode41 = new ListNode(-497, new ListNode(-475, new ListNode(-471, null)));
    static ListNode listNode42 = new ListNode(-487, new ListNode(-475, new ListNode(-465, null)));
    static ListNode listNode43 = new ListNode(-493, new ListNode(-479, new ListNode(-459, null)));
    static ListNode listNode44 = new ListNode(-490, new ListNode(-481, new ListNode(-479, null)));
    static ListNode listNode45 = new ListNode(-485, new ListNode(-466, new ListNode(-457, null)));
    static ListNode listNode46 = new ListNode(-499, new ListNode(-470, new ListNode(-469, null)));
    static ListNode listNode47 = new ListNode(-484, new ListNode(-472, new ListNode(-458, null)));
    static ListNode listNode48 = new ListNode(-498, new ListNode(-495, new ListNode(-486, null)));
    static ListNode listNode49 = new ListNode(-489, new ListNode(-461, new ListNode(-446, null)));
    static ListNode listNode50 = new ListNode(-496, new ListNode(-491, new ListNode(-410, null)));
    static ListNode listNode51 = new ListNode(-496, new ListNode(-472, new ListNode(-464, null)));
    static ListNode listNode52 = null;
    static ListNode listNode53 = new ListNode(-493, new ListNode(-493, new ListNode(-485, null)));
    static ListNode listNode54 = new ListNode(-489, new ListNode(-473, new ListNode(-470, null)));
    static ListNode listNode55 = new ListNode(-495, new ListNode(-474, new ListNode(-464, null)));
    static ListNode listNode56 = new ListNode(-500, new ListNode(-500, new ListNode(-487, null)));
    static ListNode listNode57 = new ListNode(-480, new ListNode(-465, new ListNode(-459, null)));
    static ListNode listNode58 = new ListNode(-497, new ListNode(-491, new ListNode(-490, null)));
    static ListNode listNode59 = new ListNode(-500, new ListNode(-497, new ListNode(-489, null)));
    static ListNode listNode60 = new ListNode(-500, new ListNode(-496, new ListNode(-483, null)));
    static ListNode listNode61 = new ListNode(-491, new ListNode(-483, new ListNode(-478, null)));
    static ListNode listNode62 = new ListNode(-489, new ListNode(-484, new ListNode(-483, null)));
    static ListNode listNode63 = new ListNode(-470, new ListNode(-455, new ListNode(-445, null)));
    static ListNode listNode64 = new ListNode(-487, new ListNode(-472, new ListNode(-455, null)));
    static ListNode listNode65 = new ListNode(-495, new ListNode(-488, new ListNode(-478, null)));
    static ListNode listNode66 = new ListNode(-488, new ListNode(-481, new ListNode(-479, null)));
    static ListNode listNode67 = new ListNode(-496, new ListNode(-496, new ListNode(-488, null)));
    static ListNode listNode68 = new ListNode(-497, new ListNode(-495, new ListNode(-491, null)));
    static ListNode listNode69 = new ListNode(-489, new ListNode(-487, new ListNode(-482, null)));
    static ListNode listNode70 = new ListNode(-473, new ListNode(-452, new ListNode(-449, null)));
    static ListNode listNode71 = new ListNode(-494, new ListNode(-494, new ListNode(-483, null)));
    static ListNode listNode72 = new ListNode(-494, new ListNode(-487, new ListNode(-475, null)));
    static ListNode listNode73 = new ListNode(-484, new ListNode(-480, new ListNode(-468, null)));
    static ListNode listNode74 = new ListNode(-482, new ListNode(-480, new ListNode(-474, null)));
    static ListNode listNode75 = new ListNode(-452, new ListNode(-438, new ListNode(-434, null)));
    static ListNode listNode76 = new ListNode(-499, new ListNode(-495, new ListNode(-491, null)));
    static ListNode listNode77 = new ListNode(-460, new ListNode(-456, new ListNode(-451, null)));
    static ListNode listNode78 = new ListNode(-459, new ListNode(-269, new ListNode(-255, null)));
    static ListNode listNode79 = new ListNode(-479, new ListNode(-386, new ListNode(-337, null)));
    static ListNode listNode80 = new ListNode(-492, new ListNode(-468, new ListNode(-465, null)));
    static ListNode listNode81 = new ListNode(-392, new ListNode(-198, new ListNode(-132, null)));
    static ListNode listNode82 = new ListNode(-494, new ListNode(-488, new ListNode(-481, null)));
    static ListNode listNode83 = new ListNode(-499, new ListNode(-491, new ListNode(-491, null)));
    static ListNode listNode84 = new ListNode(-499, new ListNode(-488, new ListNode(-475, null)));
    static ListNode listNode85 = new ListNode(-474, new ListNode(-455, new ListNode(-445, null)));
    static ListNode listNode86 = new ListNode(-494, new ListNode(-482, new ListNode(-465, null)));
    static ListNode listNode87 = new ListNode(-493, new ListNode(-479, new ListNode(-468, null)));
    static ListNode listNode88 = new ListNode(-499, new ListNode(-496, new ListNode(-493, null)));
    static ListNode listNode89 = new ListNode(-496, new ListNode(-492, new ListNode(-489, null)));

//    static ListNode a = new ListNode(0, null);
//    static ListNode b = new ListNode(1, null);

    public static void main(String[] args) {
        ListNode[] lists = {listNode1,
                listNode2,
                listNode3,
                listNode4,
                listNode5,
                listNode6,
                listNode7,
                listNode8,
                listNode9,
                listNode10,
                listNode11,
                listNode12,
                listNode13,
                listNode14,
                listNode15,
                listNode16,
                listNode17,
                listNode18,
                listNode19,
                listNode20,
                listNode21,
                listNode22,
                listNode23,
                listNode24,
                listNode25,
                listNode26,
                listNode27,
                listNode28,
                listNode29,
                listNode30,
                listNode31,
                listNode32,
                listNode33,
                listNode34,
                listNode35,
                listNode36,
                listNode37,
                listNode38,
                listNode39,
                listNode40,
                listNode41,
                listNode42,
                listNode43,
                listNode44,
                listNode45,
                listNode46,
                listNode47,
                listNode48,
                listNode49,
                listNode50,
                listNode51,
                listNode52,
                listNode53,
                listNode54,
                listNode55,
                listNode56,
                listNode57,
                listNode58,
                listNode59,
                listNode60,
                listNode61,
                listNode62,
                listNode63,
                listNode64,
                listNode65,
                listNode66,
                listNode67,
                listNode68,
                listNode69,
                listNode70,
                listNode71,
                listNode72,
                listNode73,
                listNode74,
                listNode75,
                listNode76,
                listNode77,
                listNode78,
                listNode79,
                listNode80,
                listNode81,
                listNode82,
                listNode83,
                listNode84,
                listNode85,
                listNode86,
                listNode87,
                listNode88,
                listNode89};
        ListNode listNode = mergeKLists(lists);
        while (null != listNode) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

//    public static ListNode mergeKLists(ListNode[] lists) {
//
//        if (0 == lists.length) {
//            return null;
//        }
//
//        ListNode[] newListNode = new ListNode[lists.length];
//        int x = 0;
//        for (int i = 0; i < lists.length; i++) {
//            if (null != lists[i]) {
//                newListNode[x] = lists[i];
//                x++;
//            }
//        }
//        lists = newListNode;
//
//        if (null == lists[0]) {
//            return null;
//        }
//
//        ListNode node;
//
//        Arrays.sort(lists, (o1, o2) -> {
//            if (null == o1 || null == o2) {
//                return 0;
//            }
//
//            if (o1.val < o2.val) {
//                return -1;
//            }
//
//            if (o1.val > o2.val) {
//                return 1;
//            }
//
//            return 0;
//        });
//
//        node = lists[0];
//        lists[0] = lists[0].next;
//
//        node.next = mergeKLists(lists);
//        return node;
//    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        if (lists.length == 1)
            return lists[0];
        if (lists.length == 2) {
            return mergeTwoLists(lists[0], lists[1]);
        }

        int mid = lists.length / 2;
        ListNode[] l1 = new ListNode[mid];
        for (int i = 0; i < mid; i++) {
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length - mid];
        for (int i = mid, j = 0; i < lists.length; i++, j++) {
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));

    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val) {
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}
